1. Field of the Invention
The present invention relates to a method for calculation in parallel of multiple fuzzy logic inference rules. The present invention concerns also a circuit architecture for implementation of the parallel calculation.
Specifically the present invention relates to a method for parallel processing of multiple fuzzy logic inference rules organized in fuzzy sets or logical functions of multiple fuzzy sets including membership functions defined in a so-called discourse universe and said rules being configured essentially as IF-THEN rules with at least one antecedent preposition and at least one consequent implication and said prepositions including at least one term of comparison between the membership functions and a plurality of input data and the terms being separated by logical operators.
2. Discussion of the Related Art
Fuzzy logic has now been established as a technique capable of supplying solutions for broad classes of control problems for which conventional techniques, e.g. those based on Boolean logic, have proven unsuited, and for providing acceptable performance at acceptable cost.
Fuzzy logic supplies a method of modelling the xe2x80x98inaccuratexe2x80x99 modes of reasoning typical of the human mind and which play an essential role in the human ability to make decisions under conditions of uncertainty.
Fuzzy logic operates on a linguistic description of reality using a particular class of variables termed xe2x80x98linguistic variablesxe2x80x99. The values of said variables include words or phrases of any natural or artificial language. Basically, to each variable is assigned a corresponding semantic meaning of the words or phrases which are used in the modelling of a given problem.
In addition, to each variable can be syntactically joined a set of values dependent upon it which can take on different meanings depending on the context in which they are employed. Said values are found starting from a primary term which represents the variable, from one of its contraries, and from a series of so-called modifiers of the primary term, as described in European patent application no. 92830095.3.
Each value assigned to a linguistic variable is represented furthermore by a so-called fuzzy set, a possibilistic distribution function which links each value of the variable corresponding definition domain known as the universe of discourse.
The functions which identify a fuzzy set in the universe of discourse of a variable are called membership functions FA. For example, a value FA=0 indicates the non-membership of the point in the fuzzy set identified by the function, while a value FA=1 indicates the certainty of membership of the point in the fuzzy set. The assembly of all the fuzzy sets of a linguistic variable is called a xe2x80x98term setxe2x80x99.
Membership functions are defined by means of a sample representation obtained by dividing the definition domain in m points and the interval [0, 1] in 1 levels.
At present, definition or storage in a fuzzy logic based electronic controller of the membership functions which identify the fuzzy sets represents one of the major constraints on development of new fuzzy logic applications and thus limits the theoretical potential of this methodology.
Indeed, if it is desired to implement the membership functions in hardware to reflect the semantics of the fuzzy concept and to obtain a correct incidence of a term in a rule, one is forced to use considerable memory space. This makes fuzzy logic advantageous only for those applications where the term set of the linguistic variable consists of a reduced number of membership functions.
The data for a membership function are normally stored in a memory word. In known devices the memory area occupied is thus negatively influenced by the number of data necessary for defining these membership functions.
In many cases it has proven sufficient to store triangular membership functions, generally not symmetrical, or trapezoid membership functions so as to reduce the amount of data necessary for their storage.
With these triangular or trapezoid membership functions, it is not at all necessary to store the values of the function at all points of the universe of discourse. It is sufficient to store only the points where the curve changes slope and the value of this slope.
Appropriate logical operationsxe2x80x94termed xe2x80x98inferentialxe2x80x99xe2x80x94which allow description of the behavior of a system with the change in input parameters are performable among the membership functions. These operations are performed by fuzzy rules which have generally a syntax of the following type:
IF X IS A, THEN Y IS B
where 1 is the input value, A and B are membership functions FA which represent system knowledge, and Y is the output value.
The part of the rule preceding the term THEN is called the xe2x80x98leftxe2x80x99 or xe2x80x98antecedentxe2x80x99 part while the following part is called xe2x80x98rightxe2x80x99 or xe2x80x98consequentxe2x80x99 part of the inference rule.
The implication between the antecedent part and the consequent part of a fuzzy rule is governed by two laws:
modus ponens: in it the truth of the implication (Th), i.e. of the consequent part of the rule, depends on that of the premise (Hp), i.e. the antecedent part of the rule;
modus tollens: in it occurrence of the implication (Th) which ensures correctness of the premise (Hp).
Adopting the modus ponens as the rule, the degree of truth of the entire rule cannot be greater than that of the antecedent part.
Since the antecedent part can be made up of one or more terms T corresponding to hypotheses of the type (F is Fxe2x80x2) on the data F and on the membership functions Fxe2x80x2 its overall degree of truth which we shall indicate by the symbol W in the following description depends on the inference operations on these same terms T.
In addition the overall degree of truth W takes on a determinate value by applying to these terms T the logical operators AND, OR and NOT.
Electronic data processing tools which allow performance of this type of operation require a particular architecture expressly dedicated to the set of inference operations which constitute the fuzzy logic computational model.
With reference to triangular or trapezoid membership functions FA such as those set forth in FIG. 1, a weight xe2x88x9d of a set of data I for an antecedent part term represented in the universe of discourse U by means of a membership function Ixe2x80x2 means the greatest value of the intersection between the input data set I and the membership function Ixe2x80x2 corresponding to said term T.
In a processor operating with fuzzy logic procedures there must be room for a circuit capable of calculating the overall degree of truth W regardless of the logical operators present.
Heretofore multivalue fuzzy logic inferences were calculated in different ways.
In a project developed at OMRON by T. Yamakawa et al. the inference processing circuit can operate analogically in parallel only on four rules whose antecedent part can have at most three terms.
In addition to this initial limitation, for design simplicity other constraints were imposed:
the terms T of the antecedent part of the rules can be separated only by logical operators AND;
the membership functions Ixe2x80x2 of the term sets of the input variables I can only have an S, Z, trapezoid or triangular shape;
the inputs are deterministic, i.e. they correspond to an individual point P in the universe of discourse U.
An architecture of H. Watanabe et al. performs in parallel all the rules for the same output variable. The user is however limited in his choice of the variables with which he can work. These can be only four input variables and two output variables out of fifty-one rules, or two input variables and one output out of one hundred two rules.
A plurality of Watanabe circuits can be connected in cascade under control of a software program in such a manner as to process more than one hundred two rules. In this case moreover it is possible to introduce a feedback of the output signal on the input of one of the components.
In like manner circuits of this type can be connected to operate with a larger number of input variables.
These architectures however involve an increase in the area of silicon occupied since they require memories of greater size.
A third known solution is the Fuzzy Micro Controller of Neural Logix in which only symmetrical and linear membership functions (triangles, trapezes, etc.) are used. Since each antecedent part of a rule can contain up to a maximum of sixteen terms, there are sixteen fuzzifiers at the input of this circuit.
The Neural Logix circuit can process up to sixty-four rules. Variables to be controlled or fedback output variables can be applied as inputs.
In this processing circuit a neural network determines the smallest of the sixteen terms contained in the antecedent part of the rule. The overall degrees of truth W of all sixty-four antecedent parts are used to calculate the maximum value by means of a circuit having a single register which is continually updated on the basis of each evaluation of the weight of each antecedent part.
Lastly, a processor known in the trade as xe2x80x98WARPxe2x80x99 and manufactured by processes sequentially up to two hundred fifty-six rules whose antecedent parts are made up of four terms.
The architecture of the inferential part was designed to calculate the degree of truth of the premise by means of parallel computation on four xcex1 values. These xcex1 values are taken simultaneously from the data memory once the input variables are known.
In the case of rules whose antecedent parts contain more than four terms T separated by logical operators the processing is carried out by dividing said antecedent parts in several antecedent sub-parts each of which contains four terms in the antecedent part allowing for the partial truth level w of each antecedent sub-part obtained by means of a feedback to the inference calculation circuit.
All the circuits heretofore available to the technicians of the industry cannot be considered absolutely effective because their efficacy depends strongly on the type of application.
In particular, the architectures which give priority to parallel processing of the inference rules in such a manner as to gain processing time lose necessarily in occupied silicon area.
On the other hand reduction of the occupied memory area by a decrease in the number of computational units causes efficiency of parallel processing to depend strongly on the number of rules associated with each individual inference operation.
Actually, if all the inferences to be processed are characterized by the same number NFR of fuzzy rules there can be a less than optimal use of available resources each time the number of processing units NPU present in the architecture is not exactly a submultiple of the number NFR of fuzzy rules.
In this case the following relationship is not satisfied:
NFR mod NPU=0
i.e. NFR is not exactly divisible by the number NPU.
In practice it is not always possible to introduce a number of inferential units equal to the number of the rules describing the process. Typically one is forced to oversize or undersize the calculation structure.
The technical problem underlying the present invention is to identify a new parallel processing method for multiple fuzzy rules which would not depend on the number of terms making up the antecedent part of the rules or the logical operators linking them.
The present invention provides simultaneous processing of several rules which can be configured dynamically in a flexible manner on the basis of the characteristics of the different applications for which the fuzzy logic is designed.
In one aspect of the invention, parallel processing is used for various rules. The rules are divided so that no antecedent has more than a certain number of elements. New rules are created for the remaining elements of an antecedent which has more than the specified number. Each rules is processed in parallel to determine a weight. The weights of the rules are then combined to determine an overall truth level. In another aspect of the invention, all of the rules process the same number of elements in an antecedent. Neutral elements are added to rules having fewer elements. In another aspect of the present invention, processing is modular so that identical processing can be performed for various rules and antecedent elements in a tree structure.
Another aspect of the invention provides an apparatus for performing parallel processing. The apparatus may include several identical processing units arranged in a tree structure for processing the antecedents of rules. The processing units receive input data and operators, determine weights based upon the input data and combine the weights using the operators. In another aspect of the invention, the processing units include a control unit for providing the proper input data and operators to the processing unit so that each rule is properly processed.